package leetcode.problems;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * _0417 Combination Sum
 * 组合总和
 * Created by gmwang on 2018/3/23
 */
public class _0417CombinationSum {
    /**
     * Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

     The same repeated number may be chosen from candidates unlimited number of times.

     Note:

     All numbers (including target) will be positive integers.
     The solution set must not contain duplicate combinations.
     Example 1:

         Input: candidates = [2,3,6,7], target = 7,
         A solution set is:
         [
             [7],
             [2,2,3]
         ]
     Example 2:

         Input: candidates = [2,3,5], target = 8,
         A solution set is:
         [
             [2,2,2,2],
             [2,3,3],
             [3,5]
         ]
     给定一组候选号码（candidates）（没有重复）和目标号码（target），
     找出candidates 候选号码总和的所有唯一组合target。

     的相同重复数目可以选自candidates 无限次数。

     注意：

     所有数字（包括target）将是正整数。
     该解决方案集不能包含重复的组合。
     */
    /**
     * 思路：
     * 1.
     * 2.
     *
     * @param
     * @return
     */
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        getResult(result, new ArrayList<Integer>(), candidates, target, 0);

        return result;
    }

    private static void getResult(List<List<Integer>> result, List<Integer> cur, int candidates[], int target, int start){
        if(target > 0){
            for(int i = start; i < candidates.length && target >= candidates[i]; i++){
                cur.add(candidates[i]);
                getResult(result, cur, candidates, target - candidates[i], i);
                cur.remove(cur.size() - 1);
            }//for
        }//if
        else if(target == 0 ){
            result.add(new ArrayList<Integer>(cur));
        }//else if
    }

    public static void main(String[] args) {
        int[] nums = {2,3,6,7};
        System.out.println(combinationSum(nums,7));
    }
}
